﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Topcoder
{
    namespace SRM529
    {
        // 250 pts DIV 2
        class PairingPawns
        { 
            public static int savedPawnCount(int[] input)
            {
                int pos = input.Length - 1;
                while (pos != 0)
                {
                    input[pos - 1] += input[pos] / 2;
                    pos--;
                }
                return input[0];
            }
        }

        // 500 pts DIV 2
        class KingSort
        {
            public static string[] getSortedList(string[] input)
            {
                List<string> res = new List<string>(input);
                IComparer<string> c = new myComparer();
                res.Sort(c);
                return res.ToArray();
            }
            public class myComparer : IComparer<string>
            {
                public int Compare(string x, string y)
                {
                    char[] separator = new char[] { ' ' };
                    string[] strx = (x).Split(separator) ;
                    string[] stry = (y).Split(separator);

                    if (strx[0] != stry[0]) return string.Compare(strx[0], stry[0]);
                    else return Roman(strx[1]) - Roman(stry[1]);
                }
            }
            public static int Roman(string r)
            {
                int res = 0;
                string[] m1 = new string[] { "IX", "VIII", "VII", "VI", "IV", "V", "III", "II", "I", "LXXX", "LXX", "LX", "XL", "L", "XXX", "XX", "X" };
                int[] m2 = new int[] { 9, 8, 7, 6, 4, 5, 3, 2, 1, 80, 70, 60, 40, 50, 30, 20, 10 };
                for (int i = 0; i < m1.Length; i++)
                { 
                    if (r.Contains(m1[i])) 
                    {
                        r = r.Replace(m1[i],"");
                        res += m2[i];
                    }
                }
                return res;
            }
        }

        // 1000 pts DIV 2
        class MinskyMysteryDiv2
        {
            public static long computeAnswer(long N)
            {
                if (N < 2) return -1;
                for (long i = 2;i * i <= N; ++i) if (N % i == 0) return i + (N / i);
                return N + 1;
            }
        }
    }
}
